package LeetCodeTest.PrimaryAlgorithmTest.String;

public class StrStr {
    /**
     * 实现strStr()函数。
     * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
     * 说明：
     * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
     * 示例 1：
     * 输入：haystack = "hello", needle = "ll"
     * 输出：2
     * 示例 2：
     * 输入：haystack = "aaaaa", needle = "bba"
     * 输出：-1
     * 示例 3：
     * 输入：haystack = "", needle = ""
     * 输出：0
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static void main(String[] args) {
        String haystack = "hello";String needle = "ll";
        haystack = "aaaaa"; needle = "bba";
        haystack = ""; needle = "";
        haystack = "a"; needle = "a";
        haystack = "mississippi"; needle = "issip";
        haystack = "mississippi"; needle = "pi";
        System.out.println(strStr(haystack,needle));
    }

    /**
     * 方法一时间复杂度和空间复杂度均很高 不推荐
     * @param haystack  字符串
     * @param needle    需要比较的字符串
     * @return          是否存在
     */
    public static int strStr(String haystack, String needle) {
        int index = 0;
        if (null == needle){
            return -1;
        }
        if ("".equals(needle)){
            return 0;
        }
        while (index <= (haystack.length() - needle.length())){
            if (haystack.charAt(index) == needle.charAt(0)){
                int i = 1;
                index++;
                while (i < needle.length()){
                    if (haystack.charAt(index) == needle.charAt(i)){
                        index++;
                        i++;
                    } else{
                        index = index - i;
                        i = 0;
                        break;
                    }
                }
                if (i == needle.length()){
                    return index - i;
                }
            }
            index++;
        }
        return -1;
    }

    /**
     * 方法二：时间复杂度和空间复杂度均很高 不推荐
     * @param haystack  字符串
     * @param needle    需要比较的字符串
     * @return          是否存在
     */
    public static int strStr1(String haystack, String needle) {
        int index = 0;
        if ("".equals(needle)){
            return 0;
        }
        while (index <= (haystack.length() - needle.length())){
            if (haystack.charAt(index) == needle.charAt(0)){
                int i = 1;
                index++;
                while (i < needle.length()){
                    if (haystack.charAt(index) == needle.charAt(i)){
                        index++;
                        i++;
                    } else{
                        index = index - i;
                        i = 0;
                        break;
                    }
                }
                if (i == needle.length()){
                    return index - i;
                }
            }
            index++;
        }
        return -1;
    }
}
